/*
Copyright 2010 Iain Surgey.

This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  

See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.

*/

#__body__


/*
==============
R_BeginEdgeFrame
==============
*/
private function R_BeginEdgeFrame ()
{
	#{d| int		v}
	
	edge_p = #{r_edges};
	surface_p = #{&surfaces[1]};
	#{surface_p->spans = -1};	// no background spans yet
	#{surface_p->flags = #[SURF_DRAWBACKGROUND]#}; // FIXME : Compiler to recognise hex
	#{surface_p->key = #[0x7FFfFFFF]#};
	r_currentkey = 0;
	
	surface_p = #{&surfaces[2]};	// background is surface 1,
								//  surface 0 is a dummy
	
// FIXME: set with memset - CAN THIS BE DONE AWAY WITH SOMEHOW??
	for (v in scr_y...ord_vrectbottom)
	{
		#{newedges[v] = -1};
		#{removeedges[v] = -1};
	}
}


/*
==============
R_ScanEdges

Input: 
newedges[] array
	this has links to edges, which have links to surfaces

Output:
Each surface has a linked list of its visible spans
==============
*/
private function R_ScanEdges ()
{
	#{d| int		iv, bottom,j}
	#{d| surf_t	*s}
	#{d| int tempv}
	#{d| float fvr}

	span_p = basespan_p;
	
// clear active edges to just the background edges around the whole screen
// FIXME: most of this only needs to be set up once
	#{edge_head.owner = -1};
	tempv = scr_x << 20;
	#{edge_head.u = tempv};
	edge_head_u_shift20 = #{edge_head.u} >> 20;
	#{edge_head.u_step = 0};
	#{edge_head.prev = -1};
	#{edge_head.next = &edge_tail};
	#{edge_head.surfs[0] = 0};
	#{edge_head.surfs[1] = 1};
	#{edge_head.nextremove = -1};
	#{edge_head.nearzi = 0};
	
	#{edge_tail.owner = -1};
	tempv = (ord_vrectright << 20) + 0xFFFFF;
	#{edge_tail.u = tempv};
	edge_tail_u_shift20 = #{edge_tail.u} >> 20;
	#{edge_tail.u_step = 0};
	#{edge_tail.prev = &edge_head};
	#{edge_tail.next = &edge_aftertail};
	#{edge_tail.surfs[0] = 1};
	#{edge_tail.surfs[1] = 0};
	#{edge_tail.nextremove = -1};
	#{edge_tail.nearzi = 0};
	
	#{edge_aftertail.owner = -1};
	#{edge_aftertail.u = -1};		// force a move
	#{edge_aftertail.u_step = 0};
	#{edge_aftertail.next = &edge_sentinel};
	#{edge_aftertail.prev = &edge_tail};
	#{edge_aftertail.surfs[0] = -1};
	#{edge_aftertail.surfs[1] = -1};
	#{edge_aftertail.nextremove = -1};
	#{edge_aftertail.nearzi = 0};

// FIXME: do we need this now that we clamp x in r_draw.c?
	#{edge_sentinel.owner = -1};
	tempv = 2000 << 24;
	#{edge_sentinel.u = tempv};		// make sure nothing sorts past this
	#{edge_sentinel.u_step = 0};
	#{edge_sentinel.next = -1};
	#{edge_sentinel.prev = &edge_aftertail};
	#{edge_sentinel.surfs[0] = -1};
	#{edge_sentinel.surfs[1] = -1};
	#{edge_sentinel.nextremove = -1};
	#{edge_sentinel.nearzi = 0};
	
//	
// process all scan lines
//
	bottom = ord_vrectbottom - 1;
	iv = 0; // compiler
	
	
	for (j in scr_y...bottom)
	{
		iv = j;
		current_iv = iv;
		fvr = iv;

	// mark that the head (background start) span is pre-included
		#{surfaces[1].spanstate = 1};

		if (#{newedges[iv]} > 4)
		{
			R_InsertNewEdges (#{newedges[iv]}, #{edge_head.next});
			#{newedges[iv] = -1};
		}
		
		
		R_GenerateSpans();

	// flush the span list if we can't be sure we have enough spans left for
	// the next scan
		if (span_p > max_span_p)
		{
			D_DrawSurfaces ();
			write("OVERFLOW");
			
		// clear the surface span pointers
			s = #{&surfaces[1]};
			while (s<surface_p) {
				#{s->spans = -1};
				s+=#{sizeof(surf_t)};
			}
			
			span_p = basespan_p;
		}
		
		if (#{removeedges[iv]} > 4) {
			R_RemoveEdges (#{removeedges[iv]});
			#{removeedges[iv] = -1};
		}
		
		
		if (#{edge_head.next} != #{&edge_tail}) {
			R_StepActiveU (#{edge_head.next});
		}
	}

// do the last scan (no need to step or sort or remove on the last scan)

	current_iv = iv;
	fvr = iv;

// mark that the head (background start) span is pre-included
	#{surfaces[1].spanstate = 1};

	if (#{newedges[iv]} > 4) {
		R_InsertNewEdges (#{newedges[iv]}, #{edge_head.next});
		#{newedges[iv] = -1};
	}

	R_GenerateSpans();

// draw whatever's left in the span list
	D_DrawSurfaces ();
}

/*
==============
R_InsertNewEdges

Adds the edges in the linked list edgestoadd, adding them to the edges in the
linked list edgelist.  edgestoadd is assumed to be sorted on u, and non-empty (this is actually newedges[v]).  edgelist is assumed to be sorted on u, with a
sentinel at the end (actually, this is the active edge table starting at
edge_head.next).
==============
*/
private function R_InsertNewEdges (edgestoadd : Int, edgelist : Int)
{
	#{s| edge_t *edgestoadd, *edgelist}
	#{d| edge_t	*next_edge}
	
	do
	{
		next_edge = #{edgestoadd->next};
		while(true) {
			if (#{edgelist->u} >= #{edgestoadd->u})
				break;
			#{edgelist=edgelist->next};
			if (#{edgelist->u} >= #{edgestoadd->u})
				break;
			#{edgelist=edgelist->next};
			if (#{edgelist->u} >= #{edgestoadd->u})
				break;
			#{edgelist=edgelist->next};
			if (#{edgelist->u} >= #{edgestoadd->u})
				break;
			#{edgelist=edgelist->next};
		}

	// insert edgestoadd before edgelist
		#{edgestoadd->next = edgelist};
		#{edgestoadd->prev = edgelist->prev};
		#{edgelist->prev->next = edgestoadd};
		#{edgelist->prev = edgestoadd};
		edgestoadd = next_edge;
	} while (edgestoadd  > 0);
}


/*
==============
R_GenerateSpans
==============
*/
private function R_GenerateSpans ()
{
	#{d| edge_t			*edge}
	#{d| surf_t			*surf}

// clear active surfaces to just the background surface
	#{surfaces[1].next = &surfaces[1]};
	#{surfaces[1].prev = &surfaces[1]};
	#{surfaces[1].last_u = edge_head_u_shift20};

// generate spans
	edge=#{edge_head.next};
	while (edge != #{&edge_tail})
	{			
		if (#{edge->surfs[0]} >= 0)
		{
		// it has a left surface, so a surface is going away for this span
			surf = #{surfaces} + (#{edge->surfs[0]}*#{sizeof(surf_t)});

			R_TrailingEdge (surf, edge);
			
			if (#{edge->surfs[1]} < 0) {
				edge=#{edge->next};
				continue;
			}
		}

		R_LeadingEdge (edge);
		edge=#{edge->next};
	}

	R_CleanupSpan ();
}

/*
==============
R_TrailingEdge
==============
*/
private function R_TrailingEdge (surf : Int, edge : Int)
{
	#{s| surf_t *surf}
	#{s| edge_t *edge}
	#{d| espan_t			*span}
	#{d| int				iu}
	
// don't generate a span if this is an inverted span, with the end
// edge preceding the start edge (that is, we haven't seen the
// start edge yet)
	#{surf->spanstate = surf->spanstate - 1};
	if (#{surf->spanstate} == 0)
	{
		
		if (surf == #{surfaces[1].next})
		{
		// emit a span (current top going away)
			iu = #{edge->u} >> 20;
			if (iu > #{surf->last_u})
			{
				span = span_p;
				span_p += #{sizeof(espan_t)};
				#{span->u = surf->last_u};
				#{span->count = iu - span->u};
				#{span->v = current_iv};
				#{span->pnext = surf->spans};
				#{surf->spans = span};
			}
			
		// set last_u on the surface below
			#{surf->next->last_u = iu};
		}
		
		#{surf->prev->next = surf->next};
		#{surf->next->prev = surf->prev};
	}
}


/*
==============
R_LeadingEdge
==============
*/
private function R_LeadingEdge (edge : Int)
{
	#{s| edge_t *edge}
	#{d| espan_t			*span}
	#{d| surf_t			*surf, *surf2}
	#{d| int				iu}
	#{d| float			fu, newzi, testzi, newzitop, newzibottom}
	var goto_newtop : Bool = false;
	surf = 0;
	surf2 = 0;
	
	while (true) {
		if (#{edge->surfs[1]} >= 0)
		{
		// it's adding a new surface in, so find the correct place
			surf = #{&surfaces[edge->surfs[1]]};
			
		// don't start a span if this is an inverted span, with the end
		// edge preceding the start edge (that is, we've already seen the
		// end edge)
			#{surf->spanstate = surf->spanstate + 1};
			if (#{surf->spanstate} == 1)
			{
				surf2 = #{surfaces[1].next};
				
				if (#{surf->key} < #{surf2->key}) {
					goto_newtop = true;
					break;
				}
				
				while(true) {
					do
					{
						surf2 = #{surf2->next};
					} while (#{surf->key} > #{surf2->key});
					
					if (#{surf->key} == #{surf2->key})
					{
						continue;
					}
					break;
				}
				
			// insert before surf2
				#{surf->next = surf2};
				#{surf->prev = surf2->prev};
				#{surf2->prev->next = surf};
				#{surf2->prev = surf};
			}
		}
		break;
	}
	
	if (goto_newtop) {
	// emit a span (obscures current top)
		iu = #{edge->u} >> 20;
		
		if (iu > #{surf2->last_u})
		{
			span = span_p;
			span_p+=#{sizeof(espan_t)};
			#{span->u = surf2->last_u};
			#{span->count = iu-span->u};
			#{span->v = current_iv};
			#{span->pnext = surf2->spans};
			#{surf2->spans = span};
		}
		#{surf->last_u = iu};
		
		#{surf->next = surf2};
		#{surf->prev = surf2->prev};
		#{surf2->prev->next = surf};
		#{surf2->prev = surf};
	}
}


/*
==============
R_CleanupSpan
==============
*/
private function R_CleanupSpan ()
{
	#{d| surf_t	*surf}
	#{d| int		iu}
	#{d| espan_t	*span}
	
// now that we've reached the right edge of the screen, we're done with any
// unfinished surfaces, so emit a span for whatever's on top
	surf = #{surfaces[1].next};
	iu = edge_tail_u_shift20;
	if (iu > #{surf->last_u})
	{
		span = span_p;
		span_p+=#{sizeof(espan_t)};
		#{span->u = surf->last_u};
		#{span->count = iu - span->u};
		#{span->v = current_iv};
		#{span->pnext = surf->spans};
		#{surf->spans = span};
	}
	
// reset spanstate for all surfaces in the surface stack
	do
	{
		#{surf->spanstate = 0};
		surf = #{surf->next};
	} while (surf > #{surfaces}+#{sizeof(surf_t)});
}

/*
==============
R_RemoveEdges
==============
*/
private function R_RemoveEdges (pedge : Int)
{
	#{s| edge_t *pedge}
	do
	{
		#{pedge->next->prev = pedge->prev};
		#{pedge->prev->next = pedge->next};
		pedge = #{pedge->nextremove};
	} while (pedge > 0);
}


/*
==============
R_StepActiveU
==============
*/
private function R_StepActiveU (pedge : Int)
{
	#{s| edge_t *pedge}
	#{d| edge_t		*pnext_edge, *pwedge}

	while (true)
	{
		while(true) {
			#{pedge->u = pedge->u + pedge->u_step};
			if (#{pedge->u} < #{pedge->prev->u}) {
				break;
			}
			pedge = #{pedge->next};
				
			#{pedge->u = pedge->u + pedge->u_step};
			if (#{pedge->u} < #{pedge->prev->u}) {
				break;
			}
			pedge = #{pedge->next};
				
			#{pedge->u = pedge->u + pedge->u_step};
			if (#{pedge->u} < #{pedge->prev->u}) {
				break;
			}
			pedge = #{pedge->next};
				
			#{pedge->u = pedge->u + pedge->u_step};
			if (#{pedge->u} < #{pedge->prev->u}) {
				break;
			}
			pedge = #{pedge->next};
		}	
		
		if (pedge == #{&edge_aftertail})
			return;
			
	// push it back to keep it sorted		
		pnext_edge = #{pedge->next};

	// pull the edge out of the edge list
		#{pedge->next->prev = pedge->prev};
		#{pedge->prev->next = pedge->next};

	// find out where the edge goes in the edge list
		pwedge = #{pedge->prev->prev};
		while (#{pwedge->u} > #{pedge->u})
		{
			pwedge = #{pwedge->prev};
		}

	// put the edge back into the edge list
		#{pedge->next = pwedge->next};
		#{pedge->prev = pwedge};
		#{pedge->next->prev = pedge};
		#{pwedge->next = pedge};

		pedge = pnext_edge;
		if (pedge == #{&edge_tail})
			return;
	}
}

/*
==============
D_DrawSurfaces

Rasterize all the span lists.  Guaranteed zero overdraw.
May be called more than once a frame if the surf list overflows (higher res)
==============
*/
private function D_DrawSurfaces()
{
	#{d| surf_t			*s}
	
	TransformVector (#{r_origin}, #{transformed_modelorg});
	
	s = #{&surfaces[1]};
	while (s<surface_p)
	{
		
		if (#{s->spans} < 4) {
			s += #{sizeof(surf_t)};
			continue;
		}
		
		r_drawnpolycount++;
		
		if ((#{s->flags} & (SURF_DRAWSKYBOX|SURF_DRAWBACKGROUND|SURF_DRAWTURB) ) == 0 )
			D_SolidSurf(s);
		else if ((#{s->flags} & SURF_DRAWSKYBOX) != 0)
			D_SkySurf(s);
		s += #{sizeof(surf_t)};
	}
}


